package LC;

/**
 * https://leetcode.com/problems/recover-binary-search-tree/description/
 * Two elements of a binary search tree (BST) are swapped by mistake.
 * Recover the tree without changing its structure.
 * Note:
 * A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
 */
public class LC_099_RecoverBinarySearchTree_BinaryTree {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(-1);
        Solution.recoverTree(head);
        System.out.println(head.left.val);
        System.out.println(head.right.val);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Solution {
        static TreeNode first;
        static TreeNode second;
        static TreeNode pre;

        static void recoverTree(TreeNode root) {
            if (root == null) return;
            inorder(root);
            if (second != null && first != null) {
                int val = second.val;
                second.val = first.val;
                first.val = val;
            }
        }

        private static void inorder(TreeNode root) {
            if (root == null) return;
            inorder(root.left);
            if (pre == null)
                pre = root;
            else {
                if (root.val < pre.val) {
                    if (first == null) first = pre;
                    second = root;
                }
                pre = root;
            }
            inorder(root.right);
        }
    }
}
